#include<stdio.h>
#include<stdlib.h>
#define max 100
#define INF 32767
#define InfoType char
typedef struct
{
	int no;
	InfoType info;
}VertexType;

typedef struct 
{
	int edges[max][max];
	int n,e;
	VertexType vexs[max];
}MatGraph;


typedef struct ANode
{
	int adjvex;
	struct ANode *nextarc;
	int weight;
}ArcNode;
typedef struct Vnode
{
	InfoType info;
	ArcNode *firstarc;
}VNode;
typedef struct
{
	VNode adjlist[max];
	int n,e;
}AdjGraph;

void Creatadj(AdjGraph *&G,int A[max][max],int n,int e)		//图
{
	int i,j;
	ArcNode *p;
	G=(AdjGraph *)malloc(sizeof(AdjGraph));
	for(i=0;i<n;i++)
	{
		G->adjlist[i].firstarc=NULL;
	}
	for(i=0;i<n;i++)
	{
		for(j=n-1;j>=0;j--)
		{
			if(A[i][j]!=0&&A[i][j]!=INF)
			{
				p=(ArcNode *)malloc(sizeof(ArcNode));
				p->adjvex=j;
				p->weight=A[i][j];
				p->nextarc=G->adjlist[i].firstarc;
				G->adjlist[i].firstarc=p;
			}
		}

	}
	G->n=n;
	G->e=e;

}

void Creatmat(MatGraph &g,int A[max][max],int n,int e)		//矩阵
{
	int i,j;
	g.n=n;
	g.e=e;
	for(i=0;i<g.n;i++)
	{
		for(j=0;j<g.n;j++)
		{
			g.edges[i][j]=A[i][j];

		}
	}
}
void Dispmat(MatGraph &g)  //矩阵
{
	int i,j;
	for(i=0;i<g.n;i++)
	{
		for(j=0;j<g.n;j++)
		{
			if(g.edges[i][j]!=INF)
				printf("%4d",g.edges[i][j]);
			else
				printf("   !");

		}
		printf("\n");

	}

}
void DispAdj(AdjGraph *G)  //表
{
	int i;
	ArcNode *p;
	for(i=0;i<G->n;i++)
	{
		p=G->adjlist[i].firstarc;
		printf("顶点%d  ",i);
		while(p!=NULL)
		{
			printf("%d[%d]->",p->adjvex,p->weight);
			p=p->nextarc;

		}
		printf("^\n");

	}
}



void DedtoryAdj(AdjGraph *&G)   //销毁
{
	int i;
	ArcNode *pre,*p;
	for(i=0;i<G->n;i++)
	{
		pre=G->adjlist[i].firstarc;
		while(pre!=NULL)
		{
			p=pre;
			pre=pre->nextarc;
			free(p);
		}
	}
	free(G);G=NULL;
}
int main()
{
	AdjGraph *G;
	MatGraph g;
	int n=6;
	int e=10;
	int A[max][max]={{0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,9,INF},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}};
	Creatmat(g,A,n,e);
	printf("邻接矩阵为：\n\n");
	Dispmat(g);
	Creatadj(G,A,n,e);
	printf("邻接表为：\n\n");
	DispAdj(G);
	printf("销毁邻接表为：\n\n");
	DedtoryAdj(G);
	if(G==NULL)
		printf("成功！\n\n");
	system("pause");
	return 0;
}
